Common and long-established methods for assessing the quality of a link in an IP network involve the use of ICMP [Internet Control Message Protocol] to send echo-reply control messages between network entities to check if a remote device is accessible and the delays involved. This method commonly made use of a program, PING [Packet Internet Groper], to check accessibility and transmission delays. The resultant data was then used to maintain routing tables for dynamic hop-by-hop routing using SNMP [Simple Network Management Protocol] over TCP/IP [Transmission Control Protocol/Internet Protocol].
Though still in widespread use, ‘pinging’ has a number of serious drawbacks as a means for determining link and router latencies (packet transit and processing delays). First, the receipt and processing of the ping and the generation of the echo-reply by the recipient requires a variable amount of processing time, dependant upon the instantaneous processing load of the recipient. Second, the receipt and processing of the echo and the computation of the transit time requires a variable amount of processing time at the sender, which also depends upon the instantaneous processing load of the sender and adds to the apparent latency of the network elements involved. Third, a ping that involves multiple hops via multiple routers using a hop-by-hop protocol may not be indicative of the following message or session transmission speed since—in a TCP/IP system—many of the packets comprising the message might take different routes to their destination as a result of dynamic routing. Moreover, the interrogation and echo packets of a ping may themselves take different routes in a hop-by-hop routing system. Fourth, pinging using hop-by-hop protocols will poorly represent the latency of an end-to-end connection established under the ATM protocol since the route negotiated for the ATM message is likely to be different to that taken by the ping. Fifth, pining is highly wasteful of network resources because:                (i) each network element must be pinged from each other element to establish and maintain a comprehensive set of routing tables,        (ii) though a control packet carrying a ping or echo may transit many intermediate nodes or routers, those intermediate devices cannot garner latency information from that packet, and        (iii) each ping involves two transits across the network, one interrogation and one echo.        
It is known for each router to maintain a router table or database that records at least some qualitative property of each link connected to a router to inform routing decisions; that is, to allow the most appropriate intermediate node or router to be selected for the forwarding of a packet or for establishing an end-to-end ATM connection. In many networks, the network manager maintains a master router table or database that records all such information for the network. Since the capacity and transmission delay (latency) of a route will vary according to traffic load and the capabilities of the links and routers in that route, router tables need constant updating. This is especially important for the connection-oriented ATM protocol where transmission quality ‘contracts’ are negotiable. The use of constantly updated routing tables at each router for the purpose of dynamically determining routing in a network is often called ‘adaptive routing’.
While latency is one of the most important quality parameters of a link, it is not the only one and it is known to record other fixed and variable characteristics of a link in a router table. For example, International patent application PCT/SE98/02345 [WO 99/33232] by Ericsson discloses an algorithm for computing a quality parameter called ‘link cost’, recording that parameter in router tables and using it for establishing connections in an ATM system. The inputs for this computation are themselves computed variables such as maximum cell transfer delay, peak-to-peak cell delay variation, available cell rate, cell loss ratio, and the like. While link latency is a vital input for such computations, the Ericsson application is silent with regard to how link latency is determined.
U.S. Pat. No. 4,771,424 to Hitachi discloses an adaptive routing system in which the queue length at a router on a link is used as a proxy for the latency of that link and router tables are maintained using that data. However, there are two important problems with this: first, the latency of the link itself is ignored so that a slow link that terminates at a fast receiver with no packet queue is seen to have zero latency and, second, interrogation/management packets must wait their turn in the queue for processing and return with the requested data.
U.S. Pat. No. 5,805,602 to Bell Atlantic Network Services, Inc discloses a method of minimising packet jitter when decoding a stream of ATM cells carrying audio or MPEG-encoded data into an IP packet stream, which method uses both the internal program clock reference [PCR] carried by the audio or MPEG data and an external clock at the receiver. However, this patent is not concerned with adaptive routing and there is no suggestion that packet jitter might be used as a proxy for link quality, or that either the variation between the PCR time and ‘absolute’ time (eg, UTS time) might be used in that way. However, this Bell Atlantic patent rightly emphasises that special care is needed when transmitting video or audio packets and, by implication, highlights the need for accurate and up-to-date data on composite route latency in a network when routes are being negotiated for such packets. Nevertheless, the Bell Atlantic patent is silent as to how either link or router latency is measured.
In a large and complex network—such as the global Internet—there may be many intermediate switches and links/trunks in a virtual circuit and the choice of route can be an important factor in end-to-end communications speed, even where all relevant switches and links are operating normally. Routing algorithms are known and widely used but tend to be computationally intensive and are generally unable to take account of rapidly varying local traffic conditions, or to handle data according to priority or bandwidth requirements. They also involve considerable cost in terms of management overheads if link latency is measured by pinging or by a proxy such as packet queue length at router ports. The alternative expedient of setting aside trunk and switch capacity to handle streaming video/audio data, or other high-priority data, is inefficient and costly in terms of the utilization of network capacity.